{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find K Closest Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting #sliding-window #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序 #滑动窗口 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findClosestElements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到 K 个最接近的元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <strong>排序好</strong> 的数组&nbsp;<code>arr</code> ，两个整数 <code>k</code> 和 <code>x</code> ，从数组中找到最靠近 <code>x</code>（两数之差最小）的 <code>k</code> 个数。返回的结果必须要是按升序排好的。</p>\n",
    "\n",
    "<p>整数 <code>a</code> 比整数 <code>b</code> 更接近 <code>x</code> 需要满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>|a - x| &lt; |b - x|</code> 或者</li>\n",
    "\t<li><code>|a - x| == |b - x|</code> 且 <code>a &lt; b</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3,4,5], k = 4, x = 3\n",
    "<strong>输出：</strong>[1,2,3,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3,4,5], k = 4, x = -1\n",
    "<strong>输出：</strong>[1,2,3,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= arr.length</code></li>\n",
    "\t<li><code>1 &lt;= arr.length&nbsp;&lt;= 10<sup>4</sup></code><meta charset=\"UTF-8\" /></li>\n",
    "\t<li><code>arr</code>&nbsp;按 <strong>升序</strong> 排列</li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= arr[i], x &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-k-closest-elements](https://leetcode.cn/problems/find-k-closest-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-k-closest-elements](https://leetcode.cn/problems/find-k-closest-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n4\\n3', '[1,2,3,4,5]\\n4\\n-1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        left = 0\n",
    "        right = len(arr) - k\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if x - arr[mid] > arr[mid+k] - x:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return arr[left:left+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr, k, x):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :type k: int\n",
    "        :type x: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if arr[0] >= x:\n",
    "            return arr[:k]\n",
    "        if arr[-1] <= x:\n",
    "            return arr[-k:]\n",
    "        ans = collections.deque(arr[:k])\n",
    "        for num in arr[k:]:\n",
    "            if abs(num - x) < abs(ans[0] - x):\n",
    "                ans.popleft()\n",
    "                ans.append(num)\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: 'List[int]', k: 'int', x: 'int') -> 'List[int]':\n",
    "        n=len(arr)\n",
    "        res=[]\n",
    "        left=0\n",
    "        right=n-1\n",
    "        \n",
    "        while (k<n):\n",
    "            if (abs(arr[left]-x))>(abs(arr[right]-x)):\n",
    "                left+=1\n",
    "            else:\n",
    "                right-=1\n",
    "            n-=1\n",
    "        for index in range(left,right+1):\n",
    "            res.append(arr[index])\n",
    "        return res\n",
    "            \n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr, k, x):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :type k: int\n",
    "        :type x: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "#         k个数一定是连续的\n",
    "#         先用二分查找到最接近数,再搜索前后k个可能位的最小\n",
    "        n=len(arr)\n",
    "        if n <=k:\n",
    "            return arr\n",
    "        left, right = 0, n - 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] == x:\n",
    "                left=mid\n",
    "                right=mid\n",
    "            elif arr[mid] < x:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        minno=0\n",
    "        for i in range(k+1,-k-1,-1):\n",
    "            if (left-i>=0) & (left-i<n):\n",
    "                if (left-i+k-1>=0) & (left-i+k-1<n):\n",
    "                    # print(arr[left-i],arr[left-i+k-1])\n",
    "                    if abs(arr[left-i-1]-x)>abs(arr[left-i+k-1]-x):\n",
    "                        minno=left-i\n",
    "        return arr[minno:minno+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: 'List[int]', k: 'int', x: 'int') -> 'List[int]':\n",
    "        while len(arr) > k:\n",
    "            if x - arr[0] <= arr[-1] - x:\n",
    "                arr.pop()\n",
    "            else:\n",
    "                arr.pop(0)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: 'List[int]', k: 'int', x: 'int') -> 'List[int]':\n",
    "        index=-1\n",
    "        for i in range(len(arr)-1):\n",
    "            if arr[i]<x and arr[i+1]>x:\n",
    "                if x-arr[i]>arr[i+1]-x:\n",
    "                    index=i+1\n",
    "                else:\n",
    "                    index=i\n",
    "            elif x==arr[i]:\n",
    "                index=i\n",
    "            elif x==arr[i+1]:\n",
    "                index=i+1\n",
    "        print(index)\n",
    "        a={}\n",
    "        for i in range(index-k,index+k+1):\n",
    "            if i>=0 and len(a)<2*k and i<len(arr):\n",
    "                if abs(arr[i]-x) in a:\n",
    "                    a[abs(arr[i]-x)].append(arr[i])\n",
    "                else:\n",
    "                    a[abs(arr[i]-x)]=[arr[i]]\n",
    "        key=list(k for k,v in a.items())  \n",
    "        value=list(v for k,v in a.items())\n",
    "        key.sort()\n",
    "        num=[]\n",
    "        for i in key:\n",
    "            a[i].sort()\n",
    "            for j in a[i]:\n",
    "                if len(num)<k:\n",
    "                    num.append(j)\n",
    "                else:\n",
    "                    break\n",
    "        num.sort()\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: 'List[int]', k: 'int', x: 'int') -> 'List[int]':\n",
    "        index=-1\n",
    "        for i in range(len(arr)-1):\n",
    "            if arr[i]<x and arr[i+1]>x:\n",
    "                if x-arr[i]>arr[i+1]-x:\n",
    "                    index=i+1\n",
    "                else:\n",
    "                    index=i\n",
    "            elif x==arr[i]:\n",
    "                index=i\n",
    "            elif x==arr[i+1]:\n",
    "                index=i+1\n",
    "        a={}\n",
    "        for i in range(index-k,index+k+1):\n",
    "            if i>=0 and len(a)<2*k and i<len(arr):\n",
    "                if abs(arr[i]-x) in a:\n",
    "                    a[abs(arr[i]-x)].append(arr[i])\n",
    "                else:\n",
    "                    a[abs(arr[i]-x)]=[arr[i]]\n",
    "        key=list(k for k,v in a.items())  \n",
    "        value=list(v for k,v in a.items())\n",
    "        key.sort()\n",
    "        num=[]\n",
    "        for i in key:\n",
    "            a[i].sort()\n",
    "            for j in a[i]:\n",
    "                if len(num)<k:\n",
    "                    num.append(j)\n",
    "                else:\n",
    "                    break\n",
    "        num.sort()\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr, k, x):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :type k: int\n",
    "        :type x: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "\n",
    "        result = heapq.nsmallest(k, arr, key=lambda y: abs(y - x))\n",
    "        # print(result)\n",
    "        return sorted(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr, k, x):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :type k: int\n",
    "        :type x: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "\n",
    "        result = heapq.nsmallest(k, arr, key=lambda y: abs(y - x))\n",
    "        # print(result)\n",
    "        return sorted(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr, k, x):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :type k: int\n",
    "        :type x: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        l = [i-x for i in arr]\n",
    "        l = sorted(l, key=lambda x: abs(x))\n",
    "        ans = l[:k]\n",
    "        ans = [i+x for i in ans]\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr, k, x):\n",
    "        minium = 0\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            minium += abs(arr[i] - x)\n",
    "        y = minium\n",
    "        for i in range(1, len(arr) - k + 1):\n",
    "            y += abs(arr[i + k - 1] - x) - abs(arr[i - 1] - x)\n",
    "            print(arr[i+k-1])\n",
    "            if y < minium:\n",
    "                minium = y\n",
    "                ans = i\n",
    "        return arr[ans:ans + k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr, k, x):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :type k: int\n",
    "        :type x: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        abs_dict = {}\n",
    "        for i in arr:\n",
    "            tmp = abs_dict.get(abs(i - x), [])\n",
    "            tmp.append(i)\n",
    "            abs_dict[abs(i - x)] = tmp\n",
    "        abs_list = list(abs_dict.keys())\n",
    "        abs_list.sort()\n",
    "        l = k\n",
    "        for i in abs_list:\n",
    "            if l > 0:\n",
    "                res.extend(abs_dict[i][:l])\n",
    "                l = k - len(res)\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        size = len(arr)\n",
    "        left = 0\n",
    "        right = size - k\n",
    "        while left < right:\n",
    "            mid = left + int((right - left)/2)\n",
    "            if x - arr[mid] > arr[mid + k] - x:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return arr[left:left+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        left=0\n",
    "        right=len(arr)-1\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if arr[mid]<x:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        re=[]\n",
    "        left=max(left-1,0)\n",
    "        right=min(len(arr)-1,left+1)\n",
    "        while len(re)!=k:\n",
    "            if left>=0 and right<=len(arr)-1:\n",
    "                d_left=abs(arr[left]-x)\n",
    "                d_right=abs(arr[right]-x)\n",
    "                if d_left<d_right:\n",
    "                    re.append(arr[left])\n",
    "                    left-=1\n",
    "                elif d_left>d_right:\n",
    "                    re.append(arr[right])\n",
    "                    right+=1\n",
    "                else:\n",
    "                    re.append(arr[left])\n",
    "                    left-=1\n",
    "            elif left<0:\n",
    "                re.append(arr[right])\n",
    "                right+=1\n",
    "            elif right>=len(arr):\n",
    "                re.append(arr[left])\n",
    "                left-=1\n",
    "        return sorted(re)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        l,r = 0,len(arr)-k\n",
    "        while l<r:\n",
    "            mid = (l+r)>>1\n",
    "            if x - arr[mid]>arr[mid+k]-x:\n",
    "                # x距离左边界远，收缩左边界\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "        return arr[l:l+k]\n",
    "\n",
    "\n",
    "        # (这个写的很失败)\n",
    "        # res = []\n",
    "        # l = 0\n",
    "        # r = len(arr)-1\n",
    "\n",
    "        # while l+1<r:\n",
    "        #     mid = (l+r)>>1\n",
    "            \n",
    "        #     if arr[mid]==x: # 找到了这个点\n",
    "        #         # 开始向左右扩展确定范围\n",
    "        #         # print(mid)\n",
    "        #         break\n",
    "        #     elif arr[mid]>x:\n",
    "        #         r = mid\n",
    "        #     elif arr[mid]<x:\n",
    "        #         l = mid\n",
    "        # if l+1>= r: #正常退出，说明没有return mid\n",
    "        #     mid = l if abs(arr[l]-x)<=abs(arr[r]-x) else r\n",
    "        # l = max(0,mid-k+1)\n",
    "        # r = min(len(arr)-1,mid+k-1)\n",
    "        # # l-r就是预选空间\n",
    "        # abss = [abs(x-arr[i]) for i in range(len(arr))]\n",
    "        # while r-l+1!=k:\n",
    "        #     # 此时res[l:r]为所选空间\n",
    "        #     print(l,r)\n",
    "        #     if abss[r]>=abss[l]:\n",
    "        #         r-=1\n",
    "        #     else:\n",
    "        #         l+=1    \n",
    "\n",
    "        # return arr[l:r+1]\n",
    "        \n",
    "        \n",
    "        # return res\n",
    "# "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        if not arr or k <= 0:\n",
    "            return []\n",
    "        n = len(arr)\n",
    "        while len(arr) > k:\n",
    "            if abs(arr[0] - x) > abs(arr[-1] - x):\n",
    "                arr.pop(0)\n",
    "            else:\n",
    "                arr.pop()\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        arr = [-10**5] + arr + [10**5]\n",
    "        idx = bisect.bisect_left(arr, x)\n",
    "        L, R = idx - 1, idx\n",
    "        for _ in range(k):\n",
    "            if x - arr[L] <= arr[R] - x:\n",
    "                L -= 1\n",
    "            else:\n",
    "                R += 1\n",
    "        return arr[L + 1:R]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        arr = [x - 10**5] + arr + [x + 10**5]\n",
    "        idx = bisect.bisect_left(arr, x)\n",
    "        L, R = idx - 1, idx\n",
    "        for _ in range(k):\n",
    "            if x - arr[L] <= arr[R] - x:\n",
    "                L -= 1\n",
    "            else:\n",
    "                R += 1\n",
    "        return arr[L + 1:R]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        def findinsertpos(nums,key):\n",
    "            l,r=0,len(nums)-1\n",
    "            while l<r:\n",
    "                mid=(l+r)//2\n",
    "                if arr[mid]<key:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid\n",
    "            return l\n",
    "\n",
    "        if x<=arr[0]:\n",
    "            return arr[:k]\n",
    "        if x>=arr[-1]:\n",
    "            return arr[-k:]\n",
    "        pos=findinsertpos(arr,x)\n",
    "        low=max(0,pos-k)\n",
    "        high=min(len(arr)-1,pos+k-1)\n",
    "        while high-low>k-1:\n",
    "            if arr[low]+arr[high]>=2*x:\n",
    "                high-=1\n",
    "            else:\n",
    "                low+=1\n",
    "        return arr[low:high+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        ll = [abs(n-x) for n in arr]\n",
    "        m = min(ll)\n",
    "        pos = ll.index(m)\n",
    "        pos_l = [pos]\n",
    "        left_dev = 1\n",
    "        right_dev = 1\n",
    "        while len(pos_l) < k:\n",
    "            left = pos-left_dev\n",
    "            right = pos+right_dev\n",
    "            if right >= len(arr):\n",
    "                pos_l.insert(0, left)\n",
    "                left_dev += 1\n",
    "            elif left < 0:\n",
    "                pos_l.append(right)\n",
    "                right_dev += 1\n",
    "            else:\n",
    "                if ll[left] <= ll[right]:\n",
    "                    pos_l.insert(0, left)\n",
    "                    left_dev += 1\n",
    "                else:\n",
    "                    pos_l.append(right)\n",
    "                    right_dev += 1\n",
    "        print(pos_l)\n",
    "        return arr[pos_l[0]:pos_l[-1]+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        unsort = heapq.nsmallest(k, arr, key=lambda t: abs(t-x))\n",
    "        return list(sorted(unsort))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: list, k: int, x: int) -> list:\n",
    "        \"\"\"\n",
    "        思路：通过逐次移动左边以及右边的指针来逐渐逼近答案\n",
    "        :param arr: 数组\n",
    "        :param k: 区间长度\n",
    "        :param x: 目标\n",
    "        :return: 最靠近目标的k个数\n",
    "        \"\"\"\n",
    "\n",
    "        res = arr\n",
    "        while len(res) > k:\n",
    "            if abs(res[0] - x) < abs(res[-1] - x) or \\\n",
    "                    (abs(res[0] - x) == abs(res[-1] - x) and res[0] < res[-1]):  # 左边小，删除右边\n",
    "                del res[-1]\n",
    "            else:\n",
    "                del res[0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        left, right = 0, len(arr) - k\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            print(left, mid, right)\n",
    "            if x - arr[mid] > arr[mid + k] - x:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return arr[left:left + k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        left,right = 0,n-k\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if x-arr[mid] > arr[mid+k]-x:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right =mid\n",
    "        \n",
    "        re = arr[right:right+k]\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        left, right = 0, len(arr) - k\n",
    "        while left < right:\n",
    "            mid = left + right >> 1\n",
    "            #这个表达式，是最关键的\n",
    "            if x - arr[mid] > arr[mid + k] - x:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return arr[left: left + k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        arr.sort(key= lambda y: abs(y - x))\n",
    "        return sorted(arr[:k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        tmp=[-float('inf')]*k\n",
    "        idx=[0]*k\n",
    "        heapify(tmp)\n",
    "        heapify(idx)\n",
    "        res=[]\n",
    "        for k,v in enumerate(arr):\n",
    "            #print(k,v,tmp,idx)\n",
    "            if -abs(v-x)==tmp[0] and k<idx[0]:\n",
    "                heappop(tmp)\n",
    "                heappush(tmp,-abs(v-x))\n",
    "                heappop(idx)\n",
    "                heappush(idx,k)\n",
    "            elif -abs(v-x)>tmp[0]:\n",
    "                heappop(tmp)\n",
    "                heappush(tmp,-abs(v-x))\n",
    "                heappop(idx)\n",
    "                heappush(idx,k)\n",
    "        for k in idx:\n",
    "            res.append(arr[k])\n",
    "        res.sort()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findClosestElements(self, arr, k, x):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :type k: int\n",
    "        :type x: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        l = 0\n",
    "        r = len(arr) - k\n",
    "        while l < r:\n",
    "            mid = (r - l) // 2 + l\n",
    "            if x - arr[mid] > arr[mid + k] - x:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return arr[l: l + k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, a: List[int], k: int, x: int) -> List[int]:\n",
    "        if x >= a[-1]: return a[-k:]\n",
    "        if x <= a[0]: return a[:k]\n",
    "        l = bisect_left(a,x) -1\n",
    "        n = len(a)\n",
    "        if x - a[l] > a[l+1] - x:\n",
    "            l +=1\n",
    "        r = l\n",
    "        for i in range(k-1):\n",
    "            #print(a[l], a[r])\n",
    "            if r == n-1:\n",
    "                l -=1\n",
    "                continue\n",
    "            if l ==0:\n",
    "                r += 1\n",
    "                continue\n",
    "            if x - a[l-1] <= a[r+1] - x:\n",
    "                l -=1\n",
    "            else:\n",
    "                r+=1\n",
    "        return a[l:r+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        left,right=0,len(arr)-k\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if x>(arr[mid]+arr[mid+k])//2:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return arr[left:left+k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]: \n",
    "        if not arr: return list()\n",
    "        \n",
    "        larger = self.findLarger(arr, x)\n",
    "        res = list()\n",
    "        left, right = larger - 1, larger\n",
    "        for _ in range(k):\n",
    "            isLeft = self.isLeftClose(arr, left, right, x)\n",
    "            if isLeft: \n",
    "                res.append(arr[left])\n",
    "                left -= 1\n",
    "            else:\n",
    "                res.append(arr[right])\n",
    "                right += 1\n",
    "        return sorted(res)\n",
    "    \n",
    "    def findLarger(self, arr :List[int], x :int) -> int:\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] <= x: left = mid\n",
    "            else: right = mid\n",
    "        if (arr[left] > x): return left \n",
    "        if (arr[right] > x): return right\n",
    "        return len(arr) - 1\n",
    "\n",
    "    def isLeftClose(self, arr :List[int], left :int, right :int, x :int) -> int:\n",
    "        if left < 0: return False\n",
    "        if right >= len(arr): return True\n",
    "        if x - arr[left] <= arr[right] - x: return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        #解题思路：\n",
    "        #arr数组已经排序好了\n",
    "        #先找到x在arr数组中可以插入的位置，再对齐进行中心扩展\n",
    "\n",
    "        n = len(arr)\n",
    "        if x >= arr[-1]:\n",
    "            return arr[n - k:]\n",
    "        elif x <= arr[0]:\n",
    "            return arr[:k]\n",
    "\n",
    "        arr = [i - x for i in arr]\n",
    "        c = bisect.bisect_left(arr,0)\n",
    "        if c - 1 >= 0 and -arr[c - 1] <= arr[c]:\n",
    "            c = c - 1\n",
    "        res = [arr[c]]\n",
    "        l = c - 1\n",
    "        r = c + 1\n",
    "\n",
    "        while len(res) != k:\n",
    "            if 0 <= l <= n and 0 <=r < n:\n",
    "                if -arr[l] <= arr[r]:\n",
    "                    res.insert(0,arr[l])\n",
    "                    l -= 1\n",
    "                else:\n",
    "                    res.append(arr[r])\n",
    "                    r += 1\n",
    "            elif 0 <= l <= n:\n",
    "                res.insert(0,arr[l])\n",
    "                l -= 1\n",
    "            else:\n",
    "                res.append(arr[r])\n",
    "                r += 1\n",
    "\n",
    "        return [i + x for i in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "\n",
    "        \n",
    "        stack = collections.deque()\n",
    "        for i,y in enumerate(arr):\n",
    "            if len(stack)<k:\n",
    "                stack.append((y,i))\n",
    "                continue \n",
    "            z,j = stack[0]\n",
    "            if abs(y-x)<abs(z-x):\n",
    "                stack.popleft()\n",
    "                stack.append((y,i))\n",
    "     \n",
    "        return [x for x,_ in stack]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n",
    "        rec = [(-abs(e-x), e) for e in arr]\n",
    "        mheap = []\n",
    "        for e in rec:\n",
    "            if len(mheap)<k:\n",
    "                heapq.heappush(mheap, e)\n",
    "            else:\n",
    "                if -e[0]<-mheap[0][0]:\n",
    "                    heapq.heappop(mheap)\n",
    "                    heapq.heappush(mheap, e)\n",
    "        res = [e[1] for e in mheap]\n",
    "        res.sort()\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
